//
// Created by liushuai on 2021/1/24.
//

#include "lengthOfLIS.h"
int lengthOfLIS(vector<int> &nums) {
  const int n = nums.size();
  vector<int> dp = vector<int>(n, 1);
  int result = 1;
  if (n == 0) {
    return 0;
  } else {
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) dp[i] = std::max(dp[i], dp[j] + 1);
      }
      if (dp[i] > result) result = dp[i];
    }
  }
  return result;
}
